package Intermediate_algorithm.SortAndSearch;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;

/*
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [start i, end i] 。
请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

作者：LeetCode
链接：https://leetcode.cn/leetbook/read/array-and-string/c5tv3/
 */
public class _06合并区间 {

    @Test
    public void test(){
        int[][] merge = merge(new int[][]{{1, 4}, {0, 4}});
        System.out.println(Arrays.deepToString(merge));
    }

    //WA   数组删除修改的问题很难解决
    //某些集合实现（如Arrays.asList()返回的ArrayList）不支持添加、删除或修改操作。
    //这类集合是固定大小的，任何试图改变其大小的操作都会抛出 UnsupportedOperationException。
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 1) return intervals;
        ArrayList<int[]> list = new ArrayList<>();
        for (int[] interval : intervals) {
            list.add(new int[]{interval[0], interval[1]});
        }
        /* 不支持增删改
        List<int[]> list = Arrays.asList(intervals);*/
        for (int i = 0; i < list.size(); i++) {
            int left = list.get(i)[0];
            int right = list.get(i)[1];
            for (int j = 0; j < list.size(); j++) {
                if (j != i){
                    if (list.get(j)[0] >= left && list.get(j)[0] <= right) {
                        right = Math.max(right, list.get(j)[1]);
                        list.set(i,new int[]{left,right});
                        list.remove(j);
                    }
                }
            }
        }
        return list.toArray(new int[list.size()][]);
    }

    //官解
    /*
    我们用数组 merged 存储最终的答案。
    首先，我们将列表中的区间按照左端点升序排序。然后我们将第一个区间加入 merged 数组中，并按顺序依次考虑之后的每个区间：
    如果当前区间的左端点在数组 merged 中最后一个区间的右端点之后，那么它们不会重合，我们可以直接将这个区间加入数组 merged 的末尾；
    否则，它们重合，我们需要用当前区间的右端点更新数组 merged 中最后一个区间的右端点，将其置为二者的较大值。
    作者：力扣官方题解
    链接：https://leetcode.cn/problems/merge-intervals/solutions/203562/he-bing-qu-jian-by-leetcode-solution/
     */
    public static int[][] merge2(int[][] intervals) {
        //排除空数组情况
        if (intervals == null || intervals.length == 0) {
            return new int[0][2];
        }

        //先将原二维数组根据区间左端点进行排序
        Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);

        //创建合并区间对象
        ArrayList<int[]> res = new ArrayList<>();

        //根据区间右端点进行合并
        //遍历数组
        for (int i = 0; i < intervals.length; i++) {
            //创建区间左右端点对象
            int left = intervals[i][0], right = intervals[i][1];
            //判断left是否与之前区间重合
            if (res.size() == 0 || intervals[i][0] > res.get(res.size() - 1)[1]) {
                //不重合 或初始res集合为空
                res.add(new int[]{left, right});
            } else {
                //重合
                //判断哪个区间右端点更大,更改重合区间右端点
                res.get(res.size() - 1)[1] = Math.max(res.get(res.size() - 1)[1], right);
            }
        }

        return res.toArray(new int[res.size()][]);
    }
}
